//给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 
//
// 示例 1: 
//
// 输入: 2
//输出: 1
//解释: 2 = 1 + 1, 1 × 1 = 1。 
//
// 示例 2: 
//
// 输入: 10
//输出: 36
//解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 
//
// 说明: 你可以假设 n 不小于 2 且不大于 58。 
// Related Topics 数学 动态规划 
// 👍 638 👎 0

package com.cute.leetcode.editor.cn;
public class IntegerBreak {
    public static void main(String[] args) {
        Solution solution = new IntegerBreak().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 可以使用解数学题的方法实现（就不用这种方法了）
         * 一个数n可以分解为i + n-i
         * 按照题目来看是返回最大的乘积 那么一种情况是i*(n-i) 但是i 和 n-i本身又可以继续分解为多个数
         * 即最终求解为F(n) = max{i*(n-i),i*F(n-i),F(i)*(n-i),F(i)*F(n-i)} 四种情况的最大值
         * 观察可知i 和 n-i为对称取值，所以i*F(n-i),F(i)*(n-i)只需要考虑一种情况就行了
         * F(i)*F(n-i)其实没有必要单独考虑了 因为i*(n-i),i*F(n-i)已经包含了所有的情况
         * 所以最终求解的就是max(i*(n-i),i*F(n-i))
         * 求解的时候可以将计算结果存储下来，否则会重复计算好多次
         * 可以使用记忆数组自顶向下，也可以使用dp自底向上
         */
        int[] topToDown;
        public int integerBreak(int n) {
            //topToDown = new int[n+1];
            int[] memory = new int[n+1];//memory[i]存储的是i分解后的最大乘积
            memory[2] = 1;
            for (int i = 3; i <=n ; i++) {
                for (int j = 1; j <= i-1 ; j++) {
                    memory[i] = Math.max(memory[i],Math.max(j*(i-j), j*memory[i-j]));
                }
            }
            return memory[n];
        }

        /**
         * 这是自顶向下的写法
         */
        public int integerBreakHelper(int n) {
            if (n == 2) return 1;
            if (topToDown[n]!=0) return topToDown[n];
            int res = -1;
            for (int i = 1; i <= n-1 ; i++) {
                res = Math.max(res, Math.max(i*(n-i), i*integerBreakHelper(n-i)));
            }
            topToDown[n] = res;
            return res;
        }

        /**
         * 贪心算法
         * 能拆3优先拆3，如果最后剩下1则取一个3补成4，剩2就是2，剩0不×
         */
        public int integerBreak3(int n) {
            if (n == 2) return 1;
            if (n == 3) return 2;
            if (n == 4) return 4;
            int three = n / 3;
            n %= 3;
            int extra = 1;
            if (n == 1) {
                three--;
                extra = 4;
            } else if(n == 2) extra = 2;
            return (int)Math.pow(3, three) * extra;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}